/**
 * @Author Fizz Pu
 * @Date 2020/11/7 下午5:03
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

// dp问题, 和图像压缩问题很像
// f(i)表示某个最大子段和序列中, 以第i个元素结尾
// 第i个元素是否是最大子段和序列, 取决于f(i-1)
// f(i-1) < 0, 子段和序列必然减小, a[i]. f(i-1) > 0, 要么是 a[i], 要么是a[i]+ f(i-1), 要么是a[i]

// 分治思路

// 一分为2, 最大字段和要么在前面, 要么在后面, 要么在中间
// 在前面的话, 在后面的话, 可以用递归解决
// 在中间的话, 前后之和


public class Leeoffer42 {
    public int maxSubArray(int[] nums) {
        /*
        if(nums == null || nums.length <= 0) throw new IllegalArgumentException();
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for(int i = 1; i < nums.length; ++i){
            // if(dp[i-1] < 0)dp[i] = nums[i];
            // else dp[i] = Math.max(nums[i], nums[i] + dp[i-1]);
            dp[i] = Math.max(nums[i], nums[i] + dp[i-1]);
        }
        // return dp[nums.length-1]; 神坑
        int maxValue = Integer.MIN_VALUE;
        for(int j = 0; j < dp.length; ++j){
            if(dp[j] > maxValue)maxValue = dp[j];
        }
        return maxValue;*/
        if(nums == null || nums.length <= 0) throw new IllegalArgumentException();
        return  helper(nums, 0, nums.length-1);

    }

    private int helper(int []  nums, int start, int end){
        if(nums == null || nums.length <= 0) throw new IllegalArgumentException();

        if(start == end)return nums[start];

        // int middle = start + (end - start) >> 1;
        int middle = start + (end - start) / 2;
        int leftSums = helper(nums,start, middle);
        int rightSums = helper(nums,middle+1, end);
        int leftRightSums;

        int lsums = Integer.MIN_VALUE, temp = 0;
        for(int i = middle; i >= start; i--){
               temp += nums[i];
               if(temp > lsums)lsums = temp;
        }

        int rsums = Integer.MIN_VALUE;
        temp = 0;
        for(int j = middle+1; j <= end; j++){
            temp += nums[j];
            if(temp > rsums) rsums = temp;
        }
        //   maxValue = Math.max(Math.max(leftSums, rightSums), leftSums + rightSums);
        leftRightSums = rsums + lsums;

        return Math.max(Math.max(leftSums, rightSums), leftRightSums);
    }



    public static void main(String[] args) {
        Leeoffer42 leeoffer42 = new Leeoffer42();
        System.out.println(leeoffer42.maxSubArray(new int[] {1,2,3}));
        System.out.println(leeoffer42.maxSubArray(new int[] {-1,-2,-3}));
        System.out.println(leeoffer42.maxSubArray(new int[] {-1,2,-3}));
        System.out.println(leeoffer42.maxSubArray(new int[] {2}));
        System.out.println(leeoffer42.maxSubArray(new int[] {-2}));
        System.out.println(leeoffer42.maxSubArray(new int[] {-2,1,-3,4,-1,2,1,-5,4}));
        System.out.println(leeoffer42.maxSubArray(new int[0]));
        System.out.println(leeoffer42.maxSubArray(null));
    }
}
